/**
 * 222. 完全二叉树的节点个数
 * https://leetcode-cn.com/problems/count-complete-tree-nodes/
 */
public class Solutions_222 {
    public static void main(String[] args) {
        String treeStr = "[1 2 3 4 5 6]";
        TreeNode root = MyTreeNodeUtils.deserialize(treeStr);
        int result = countNodes(root);
        System.out.println(result);
    }

    /**
     * 利用完全二叉树的特征，采用二分查找的思想
     *      右子树深度与左子树深度相同时，左子树一定是一棵满二叉树
     *          左子树的节点个数可以根据深度计算得到，并分解为子问题，递归到右子树中
     *      右子树深度与左子树深度不同时，右子树一定是一棵满二叉树
     *          右子树的节点个数可以根据深度计算得到，并分解为子问题，递归到左子树中
     * 满二叉树存在的规律
     *   深度（层）：1  2  3  4   5   6
     * 节点（个数）：1  3  7  15  31  63
     *  当前层节点：1  2  4  8   16  32
     * 计算公式：共 n 层的满二叉树，共有节点
     *      Math.pow(2, n) - 1
     *      (1 << n) - 1
     */
    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 左子树的深度永远大于等于右子树的深度
        int leftDepth = curDepth(root.left);
        int rightDepth = curDepth(root.right);

        if (leftDepth == rightDepth) {
            // 左子树的节点个数 = 1 << leftDepth - 1
            int count = (1 << leftDepth) - 1;
            // 深度相同时，递归进入右子树，因为左子树一定是满的节点
            // 节点个数 = 左子树节点个数 + 右子树节点个数 + 当前节点的 1 个
            return count + countNodes(root.right) + 1;
        }
        // 深度不同时，递归进入左子树，因为右子树一定是满的节点
        int count = (1 << rightDepth) - 1;
        return count + countNodes(root.left) + 1;
    }

    /**
     * 完全二叉树计算深度
     * 左子树的深度永远大于等于右子树的深度
     * 即有左子节点，不一定有右子节点
     * 有右子节点，那么一定有左子节点
     */
    public static int curDepth(TreeNode node) {
        int res = 0;
        while (node != null) {
            res ++;
            // 往左子树深入
            node = node.left;
        }
        return res;
    }
}
